package main.Q1001_1100;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

public class Q1041_1050 {
	public static void main(String[] args) {
		System.out.println("Question1041：");
		System.out.println("Question1042：");
		System.out.println("Question1043：分隔数组以得到最大和");
		System.out.println("Question1044：");
		System.out.println("Question1045：");
		System.out.println("Question1046：最后一块石头的重量");
		System.out.println("Question1047：删除字符串中的所有相邻重复项");
		System.out.println("Question1048：");
		System.out.println("Question1049：");
		System.out.println("Question1050：");
	}
}

class Question1043 {
	public int maxSumAfterPartitioning(int[] arr, int k) {
		int n = arr.length;
		int[] dp = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			int max = arr[i - 1];
			for (int j = i - 1; j >= 0 && j >= i - k; j--) {
				dp[i] = Math.max(dp[i], dp[j] + max * (i - j));
				if (j > 0) {
					max = Math.max(max, arr[j - 1]);
				}
			}
		}
		return dp[n];
	}
}

class Question1046 {
	public int lastStoneWeight(int[] stones) {
		List<Integer> list = new ArrayList<>();
		for (int weight : stones) list.add(weight);
		while (list.size() > 1) {
			Collections.sort(list);
			int size = list.size();
			int first = list.get(size - 1), second = list.get(size - 2);
			list.remove(size - 1);
			list.remove(size - 2);
			if (first != second) {
				list.add(first - second);
			}
		}
		if (list.size() == 0) return 0;
		else return list.get(0);
	}
}

class Question1047 {
	public String removeDuplicates(String s) {
		Stack<Character> stack = new Stack<>();
		for (int i = 0; i < s.length(); i++) {
			if (stack.isEmpty()) {
				stack.push(s.charAt(i));
			} else if (stack.peek() == s.charAt(i)) {
				stack.pop();
			} else {
				stack.push(s.charAt(i));
			}
		}
		StringBuffer result = new StringBuffer();
		while (!stack.isEmpty()) {
			result.append(stack.pop());
		}
		return result.reverse().toString();
	}
}